class Solution:
    def permuteUnique(self, nums):
        nums.sort()

        used = [False] * len(nums)
        path = []
        ans = []

        def dfs(nums):
            if len(path) == len(nums):
                ans.append(list(path))
                return

            for i in range(len(nums)):
                if used[i]:
                    continue

                #  新添加的剪枝逻辑，固定相同的元素在排列中的相对位置 
                if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                    continue
                
                path.append(nums[i])
                used[i] = True
    
                dfs(nums)
    
                path.pop()
                used[i] = False

        dfs(nums)
        return ans


if __name__ == '__main__':
    s = Solution()
    ans = s.permuteUnique([1,1,2])
    print(ans)